1. Field of the Invention
The present invention relates to a random number generator.
2. Background of the Related Art
In general, a multiplicative linear congruential pseudorandom number generator is often employed for software routines. A random number represents a number selected from a number set where the same probability is assigned to all the numbers in the number set.
The random number generated by a computer using a big cycle is called a pseudorandom number. Such a random number generator for generating pseudo random numbers is applicable to a variety of fields including computer programming, simulation and network routing. Among them, the multiplicative linear congruential pseudorandom number generator is most widely employed.
Based on the thesis xe2x80x9cHardware implementation of the Lehmer random number generatorxe2x80x9d (IEE Proc.-Compute. Digit. Tech., Vol. 143, p93-95, January 1996) disclosed by A. P. Paplinski and N. Bhattacharjee, the principle of the Lehmer random number generator and a conventional hardware implementation will now be described. A Lehmer generator is a method where a random number generator is implemented in software, and the principle of the Lehmer generator is as follows.
First, a integer pseudorandom number row of z(1), z(2), z(3), . . . is generated as Equation 1:
xe2x80x83z(nxe2x88x921)=f(z(n)), n=1, 2, 3, . . .xe2x80x83xe2x80x83(1).
In Equation 1, a generation function F(xc2x7) is defined as follows in Equation 2:
r=f(z)=axc2x7z mod M, zxcex51, 2, . . . Mxe2x88x921xe2x80x83xe2x80x83(2).
At this time, for the Lehmer generator, Mersenne prime M=231xe2x88x921, and a=75=16807 are satisfied. That is, a 15-bit binary system satisfies a14:0={100000110100111}, and a random number z(z) is an integer implemented in 31 bits.
Using a binary digit multiplication mod M as shown in Equation 2, a parallelized version of algorithm is considered to generate a previous random number z to a subsequent random number r.
To explain a hardware implementation of such a number algorithm, it is convenient to distinguish a number from its corresponding binary system. If a is an integer, a""s (n+1)-bit binary representation may be expressed in an:0. If a matrix is applied, a can be implemented using a scalar product of an:0 and 2""s weight Wn:0 vector as follows in Equation 3:                     a        =                                            a                              n                :                0                                      ·                          W                              n                :                0                                              =                                    ∑                              i                =                0                            n                        ⁢                                          a                i                            ·                                                2                  n                                .                                                                        (        3        )            
In Equation 3, an:0={an anxe2x88x921 . . . a1 a0} denotes a numeral Equation of a{axcex5{0,1}}, and Wn:0={2n 2nxe2x88x921 . . . 21 20} denotes a vector of binary digit weight.
Using Equation 3, a number multiplication can be expressed in a Silvester resultant matrix by a matrix product of a multiplier and a multiplicand thereof. If an m-bit multiplicand is Zmxe2x88x921:0={Zmxe2x88x921 Zmxe2x88x922 . . . Z1 Z0}, the product of the two numbers a and z may be expressed in a binary matrix as follows in Equation 4:
xe2x80x83axc2x7z=an:0xc2x7(z)nxc2x7wn+mxe2x88x921:0xe2x80x83xe2x80x83(4).
In Equation 4, (z)n is a (n+1)xc3x97(n+m) Silvester resultant matrix (i.e., a convolution matrix), and it is formed from a shifted number Zmxe2x88x921:0 as follows in Equation 5:                                           (            𝓏            )                    n                =                                                                              [                                                                                                              𝓏                                                      m                            -                            1                                                                                                                                                𝓏                                                      m                            -                            2                                                                                                                      ⋯                                                                                              𝓏                          0                                                                                                                      xe2x80x83                                                                                                                      xe2x80x83                                                                                                                                                              xe2x80x83                                                                                                                      𝓏                                                      m                            -                            1                                                                                                                                                𝓏                                                      m                            -                            2                                                                                                                      ⋯                                                                                              𝓏                          0                                                                                            0                                                                                                                                      xe2x80x83                                                                                            0                                                                    ⋯                                                                                                                          xe2x80x83                                                    ⁢                          ⋯                                                                                                                      xe2x80x83                                                                                                                      xe2x80x83                                                                                                                                                              xe2x80x83                                                                                                                      xe2x80x83                                                                                                                      𝓏                                                      m                            -                            1                                                                                                                                                𝓏                                                      m                            -                            2                                                                                                                      ⋯                                                                                              𝓏                          0                                                                                                      ]                                ⁢                                  xe2x80x83                                                                              ⟵                                      xe2x80x83                                    ⁢                  n                                +                                  m                  ⁢                                      xe2x80x83                                    ⟶                                                      ⁢            n                    +          1.                                    (        5        )            
In Equation 5, the large parenthesis is used to represent the resultant matrix and the zero values form an appropriate triangle.
In the Lehmer generator, m=31, n=14 so that the number a14:0 is a magnitude of 1xc3x9715, in Equation 4. The magnitude of the resultant matrix (z)n is 15xc3x9745 and consequently the product of a and z is expressed in 1xc3x9745 number.
Generally, Equation 4 can be considered as a parallelized Equation of a product of two numbers. The respective rows of the above resultant Equation represents a shifted number Zmxe2x88x921:0 multiplied by respective digits of a multiplier, and the respective columns of the resultant Equation 5 are added up to provide a pseudorandom number result.
The subsequent step of the algorithm determines a residue obtained after dividing axc2x7z by M=231xe2x88x921. In other words, a mod M operation is carried out. To expand the above product as shown in Equation 6, the resultant matrix is divided into two dependant matrixes: C with a magnitude of (n+1)xc3x97n in the left; and D with a magnitude of (n+1)xc3x97m in the right of Equation 7. Here, q denotes quotient and r denotes residue.
xe2x80x83axc2x7z =qxc2x7M+rxe2x80x83xe2x80x83(6)
                                                                                          (                  𝓏                  )                                n                            =                              xe2x80x83                            ⁢                              [                                                                                                    𝓏                                                  m                          -                          1                                                                                                            ⋯                                                                                      𝓏                                                  m                          -                          n                                                                                                            ❘                                                                                      𝓏                                                  m                          -                          n                          -                          1                                                                                                            ⋯                                                                                      𝓏                        0                                                                                                            xe2x80x83                                                                                                            xe2x80x83                                                                                                            xe2x80x83                                                                                                                        0                                                                                      xe2x80x83                                                                                    ⋯                                                              ❘                                                                                      𝓏                                                  m                          -                          n                          -                          2                                                                                                            ⋯                                                                                      𝓏                        1                                                                                                            xe2x80x83                                                                                                            𝓏                        0                                                                                    0                                                                                                  ⋮                                                              ⋯                                                                                      𝓏                                                  m                          -                          1                                                                                                            ❘                                                              ⋮                                                                                      xe2x80x83                                                                                                            xe2x80x83                                                                                    ⋯                                                              ⋯                                                              ⋯                                                                                                  0                                                              ⋯                                                              0                                                              ❘                                                                                      𝓏                                                  m                          -                          1                                                                                                            ⋯                                                                                      xe2x80x83                                                                                    ⋯                                                                                      𝓏                        1                                                                                                            𝓏                        0                                                                                            ]                                                                                        =                              xe2x80x83                            ⁢                              [                                  C                  ❘                  D                                ]                                                                        (        7        )            
By combining Equations 4 and 6, Equation 8 is obtained as follows:                                                                         a                ·                z                            =                              xe2x80x83                            ⁢                                                a                                      n                    :                    0                                                  ·                                                      (                    z                    )                                    n                                ·                                  w                                                            n                      +                      m                      -                      1                                        :                    0                                                                                                                          =                              xe2x80x83                            ⁢                                                a                                      n                    :                    0                                                  ·                                  [                                                                                    C                                                                    D                                                                              ]                                ·                                  w                                                            n                      +                      m                      -                      1                                        :                    0                                                                                                                                          =                                  xe2x80x83                                ⁢                                                                            a                                              n                        :                        0                                                              ·                    C                    ·                                          w                                                                        n                          -                          1                                                :                        0                                                              ·                                          2                      m                                                        +                                      D                    ·                                          w                                                                        m                          -                          1                                                :                        0                                                                                                        )                                                                                          =                                  xe2x80x83                                ⁢                                                                            a                                              n                        :                        0                                                              ·                    C                    ·                                          w                                                                        n                          -                          1                                                :                        0                                                              ·                                          2                      m                                                        -                                      C                    ·                                          w                                                                        n                          -                          1                                                :                        0                                                                              +                                      D                    ·                                          w                                                                        m                          -                          1                                                :                        0                                                                              +                                      C                    ·                                          w                                                                        n                          -                          1                                                :                        0                                                                                                        )                                                                                                            =                                      xe2x80x83                                    ⁢                                                                                    a                                                  n                          :                          0                                                                    ·                      C                      ·                                              w                                                                              n                            -                            1                                                    :                          0                                                                    ·                      M                                        +                                          D                      ·                                              w                                                                              m                            -                            1                                                    :                          0                                                                                      +                                          C                      ·                                              w                                                                              n                            -                            1                                                    :                          0                                                                                                                    )                            .                                                          (        8        )            
Here, a relation of Wn+mxe2x88x921:0=Wnxe2x88x921:0xc2x72m+Wmxe2x88x921:0 was used. Considering an integer q, Equation 9 is obtained as follows:
(qxc2x7M+r)mod M=r mod Mxe2x80x83xe2x80x83(9)
Equation 1 may be incorporated in Equation 10.                                                         r              =                              xe2x80x83                            ⁢                                                (                                      a                    ·                    z                                    )                                ⁢                                  xe2x80x83                                ⁢                mod                ⁢                                  xe2x80x83                                ⁢                M                                                                                        =                              xe2x80x83                            ⁢                                                                    a                                          n                      :                      0                                                        (                                                            D                      ·                                              w                                                                              m                            -                            1                                                    :                          0                                                                                      +                                          C                      ·                                              w                                                                              n                            -                            1                                                    :                          0                                                                                                      ⁢                                      xe2x80x83                                    )                                ⁢                                  xe2x80x83                                ⁢                mod                ⁢                                  xe2x80x83                                ⁢                M                                                                                        =                              xe2x80x83                            ⁢                                                                    a                                          n                      :                      0                                                        ⁡                                      (                                                                  D                        ·                                                  w                                                                                    m                              -                              1                                                        :                            0                                                                                              +                                                                        [                                                                                                                    0                                                                                            C                                                                                                              ]                                                ·                                                  w                                                                                    m                              -                              1                                                        :                            0                                                                                                                )                                                  ⁢                                  xe2x80x83                                ⁢                mod                ⁢                                  xe2x80x83                                ⁢                M                                                                        (        10        )            
Eventually, Equation 11 can be obtained as follows:
xe2x80x83r=(an:0xc2x7Exc2x7wmxe2x88x921:0)mod Mxe2x80x83xe2x80x83(11).
Here, E is formed of a (n+1)xc3x97m circulation convolution matrix as shown as follows in Equation 12:                     "AutoLeftMatch"                                                            E                =                                                      D                    +                                          [                                                                                                    0                                                                                C                                                                                              ]                                                        =                                                                                    [                                                                                                                                            𝓏                                                                  m                                  -                                  n                                  -                                  1                                                                                                                                                    ⋯                                                                                                                      𝓏                                0                                                                                                                                                    𝓏                                                                  m                                  -                                  1                                                                                                                                                                                    𝓏                                                                  m                                  -                                  2                                                                                                                                                    ⋯                                                                                                                      𝓏                                                                  m                                  -                                  n                                                                                                                                                                                                                                        𝓏                                                                  m                                  -                                  n                                  -                                  2                                                                                                                                                    ⋯                                                                                                                      𝓏                                1                                                                                                                                                    𝓏                                0                                                                                                                                                    𝓏                                                                  m                                  -                                  1                                                                                                                                                    ⋯                                                                                                                      𝓏                                                                  m                                  -                                  n                                  +                                  1                                                                                                                                                                                                        ⋮                                                                                                                      xe2x80x83                                                                                                                    ⋮                                                                                      ⋮                                                                                      ⋮                                                                                                                      xe2x80x83                                                                                                                    ⋮                                                                                                                                                                          𝓏                                                                  m                                  -                                  2                                                                                                                                                    ⋯                                                                                                                      𝓏                                                                  n                                  -                                  1                                                                                                                                                                                    𝓏                                                                  n                                  -                                  2                                                                                                                                                                                    𝓏                                                                  n                                  -                                  3                                                                                                                                                    ⋯                                                                                                                      𝓏                                                                  m                                  -                                  1                                                                                                                                                                                                                                        𝓏                                                                  m                                  -                                  1                                                                                                                                                    ⋯                                                                                                                      𝓏                                n                                                                                                                                                    𝓏                                                                  n                                  -                                  1                                                                                                                                                                                    𝓏                                                                  n                                  -                                  2                                                                                                                                                    ⋯                                                                                                                      𝓏                                0                                                                                                                                    ]                                                                                              ⟵                                                      xe2x80x83                                                    ⁢                          n                          ⁢                                                      xe2x80x83                                                    ⟶                                                ⁢                                                  xe2x80x83                                                                                      .                                                                                                                                            ⟵                                      xe2x80x83                                    ⁢                  m                  ⁢                                      xe2x80x83                                    ⟶                                ⁢                                  xe2x80x83                                                                                        (        12        )            
At this time, considering that the multiplier a is a binary system wherein a corresponding bit for a14, a8, a7, a5, a2, a1, a0 is xe2x80x9c1xe2x80x9d, Equation 11 can be written as Equation 13 as follows:                                                         r              =                              xe2x80x83                            ⁢                                                (                                                            a                                              14                        :                        0                                                              ·                    E                    ·                                          w                                              30                        :                        0                                                                              )                                ⁢                                  xe2x80x83                                ⁢                mod                ⁢                                                      xe2x80x83                                    ⁢                                      xe2x80x83                                                  ⁢                                  M                  .                                                                                                        =                              xe2x80x83                            ⁢                                                                    (                                                                  E                                                  14                          :                                                                    +                                              E                                                  8                          :                                                                    +                                              E                                                  7                          :                                                                    +                                              E                                                  5                          :                                                                    +                                              E                                                  2                          :                                                                    +                                              E                                                  1                          :                                                                    +                                              E                                                  0                          :                                                                                      )                                    ·                                      w                                          30                      :                      0                                                                      ⁢                                  xe2x80x83                                ⁢                mod                ⁢                                                      xe2x80x83                                    ⁢                                      xe2x80x83                                                  ⁢                M                                                                        (        13        )            
At this time, since (1 1 1)2=(1 0 0 xe2x88x921)2 is satisfied, three rows from the quotient a can be replaced by +1 and xe2x88x921 in an appropriate position. Therefore, the finally implemented formula can be expressed as Equation 14 as follows:
r=(E14:+E8:+E7:+E5:+E3:xe2x88x92E0:)xc2x7w30:0mod Mxe2x80x83xe2x80x83(14 ).
In Equation 14, matrix for E values can be expressed as Equation 15.   "AutoLeftMatch"                                          [                                                                                E                                          14                      :                                                                                                                                        E                                          8                      :                                                                                                                                        E                                          7                      :                                                                                                                                        E                                          5                      :                                                                                                                                        E                                          3                      :                                                                                                                                        E                                          0                      :                                                                                            ]                    =                      [                                                                                𝓏                    16                                                                                        𝓏                    15                                                                    ⋯                                                                      𝓏                    23                                                                                        𝓏                    22                                                                                        𝓏                    21                                                                                        𝓏                    20                                                                                        𝓏                    19                                                                                        𝓏                    18                                                                                        𝓏                    17                                                                                                                    𝓏                    22                                                                                        𝓏                    21                                                                    ⋯                                                                      𝓏                    29                                                                                        𝓏                    28                                                                                        𝓏                    27                                                                                        𝓏                    26                                                                                        𝓏                    25                                                                                        𝓏                    24                                                                                        𝓏                    23                                                                                                                    𝓏                    23                                                                                        𝓏                    22                                                                    ⋯                                                                      𝓏                    30                                                                                        𝓏                    29                                                                                        𝓏                    28                                                                                        𝓏                    27                                                                                        𝓏                    26                                                                                        𝓏                    25                                                                                        𝓏                    24                                                                                                                    𝓏                    25                                                                                        𝓏                    24                                                                    ⋯                                                                      𝓏                    1                                                                                        𝓏                    0                                                                                        𝓏                    30                                                                                        𝓏                    29                                                                                        𝓏                    28                                                                                        𝓏                    27                                                                                        𝓏                    26                                                                                                                    𝓏                    27                                                                                        𝓏                    26                                                                    ⋯                                                                      𝓏                    3                                                                                        𝓏                    2                                                                                        𝓏                    1                                                                                        𝓏                    0                                                                                        𝓏                    30                                                                                        𝓏                    29                                                                                        𝓏                    28                                                                                                                    𝓏                    30                                                                                        𝓏                    29                                                                    ⋯                                                                      𝓏                    6                                                                                        𝓏                    5                                                                                        𝓏                    4                                                                                        𝓏                    3                                                                                        𝓏                    2                                                                                        𝓏                    1                                                                                        𝓏                    0                                                                        ]                                                (          15          )                    
Therefore, the Lehmer algorithm for generating a pseudorandom number can be solved by adding or subtracting mod M of six 31-bit values. The respective numbers are appropriately circulated present random number z.
A hardware implementation of Equation 14 will now be described in detail, using Equation 14 to describe addition and subtraction of the six 31-bit values of mod M. First, it should be understood that the mod M operation is carried out in relation to addition and subtraction of the two m-bit numbers. Assuming that the two numbers added mod M are amxe2x88x921:0 and bmxe2x88x921:0. Further, assume that smxe2x88x921:0 and dm are a sum outputted from the adder and an output carry, respectively, and Equation 16 can be satisfied as follows.
xe2x80x83amxe2x88x921:0+bmxe2x88x921:0=dm2m+smxe2x88x921:0xe2x80x83xe2x80x83(16).
Here, in order to carry out all the addition and subtraction, the output carry dmxcex5{xe2x88x921, 0, +1} is satisfied. If the output carry is not xe2x80x9c0xe2x80x9d, M is subtracted from the mod M operation result so that Equation 17 is obtained as follows:
(dm2m+smxe2x88x921:0)mod M=smxe2x88x921:0+dm2mxe2x88x92dm(2mxe2x88x921)xe2x80x83xe2x80x83(17).
Equation 18 is then obtained.
(amxe2x88x921:0+bmxe2x88x921:0)mod M=smxe2x88x921:0+dmxe2x80x83xe2x80x83(18)
Thus, the operation of Equation 14 equals the calculation of Equation 15 in which the number of respective rows are calculated in the matrix. Here, one of six elements in the each row is subtracted and the number of the elements in the each row varies from xe2x88x921 to 5.
In Equation 18, one problem lies in design of circuit to express the number in form of the output carry bit propagated in the subsequent position and the sum bits. Considering the input carry bit calculation required to complete the operation, Equation 19 is provided as follows:
(Za+Zb+Zc+Zd+Zexe2x88x92Zf+C1+C2xe2x88x92C3)=2(d1+d2xe2x88x92d3+d4)+S4xe2x80x83xe2x80x83(19).
In Equation 19, za is bits related to an i""th row of the matrix (Equation 15), and ci and di are an input carry and an output carry, respectively. Also, s4 denotes a sum bit.
The circuit implementing Equation 19 carries out information compression in proportion of 9:5. Nine input bits and five output bits denote numbers ranging from xe2x88x922 to +7, respectively. Equation 19 can be converted into a set of three input elements and two output sums. Including the final carry-propagation adder, the implemented formula may be incorporated in Equation 20 as follows.
xcexa31: za+zb+zc=2d1+s1
xcexa32: s1+zd+zc=2d2+s2
xcexa33: s2xe2x88x92zfxe2x88x92c3=xe2x88x922d3+s3
xcexa34: s3+c1+c2=2d4s4
xcexa35: s4+c4+c5=2d5+rxe2x80x83xe2x80x83(20).
FIG. 1 illustrates a related art bit generator i for generating an i""th bit in the Lehmer generator to implement Equation 20. As shown in FIG. 1, the input signals za, . . . , zi in the drawing are replaced by respective entries of i""th row in the matrix (Equation 15), and the input output signals c1, d1 are replaced by cij, cji+1.
As shown in FIG. 1, the bit generator of the related art Lehmer generator includes a first carry-save adder 101 receiving and adding first, second and third signals zi+17, zi+23, zixe2x88x927 of an i""th column in the circulation convolution matrix (i.e, Equation 15) and generating a 1-bit sum and 1-bit output carries C1, i+1. A second carry-save adder 102 receives the sum outputted from the first carry-save adder 101 and fourth and fifth signals zixe2x88x925, zixe2x88x923 of the i""th column, adds the three input signals, and generates a 1-bit sum and 1-bit output carries C2, i+1. A carry-propagate subtractor 103 subtracts a sixth signal zi of the i""th column and input carry bits C3,i received from a carry-propagate subtractor (not shown) of an ixe2x88x921""th bit generator from the sum outputted from the second carry-save adder 102. A third carry-save adder 104 adds the sum outputted from the carry-propagate subtractor 103 and two input carries C1,i, C2,i received from the first and second carry-save adders of the ixe2x88x921""th bit generator (not shown) and generates the 1-bit sum and 1-bit output carries C4,i+1. Finally, a carry-propagate adder 105 adds the sum outputted from the third carry-save adder 104 and two input carries C4,i, C5,i, received from the third carry-save adder and the carry-propagate adder (not shown) of the ixe2x88x921""th bit generator, and generates an i""th bit ri and output carry C5,i+1 of the 31-bit random number.
FIG. 2 is a block diagram showing 31 related art bit generators connected in parallel in a random number generator to generate a 31-bit random number r30:0. As shown in FIG. 2, the random number generator allows the output carry of the most significant bit generator (30) to be applied to the least significant bit generator (0) to perform the mod M operation as disclosed in Equation 18.
The operating steps of the related art random number generator will now be described. The 0th bit generator (0) to 30th bit generator (30) generate 1-bit data respectively using the same process described above. Thus, 31-bit random numbers r30:0 are generated. The process performed by an i""th bit generator will be described as an example.
To generate the i""th bit, the i""th bit generator receives 6 entries of the i""th column in the matrix (Equation 15). First, the first carry-save adder 101 receives the first, second and third signals Zi+17, Zixe2x88x9223, Zixe2x88x927 of an i""th column, adds up the three input signals and generates the 1-bit sum and 1-bit output carries S, and C1, i+1, respectively. The second carry-save adder 102 receives the sum outputted from the first carry-save adder 101 and fourth and fifth signals Zixe2x88x925, Zixe2x88x923 of the i""th column, adds the three input signals, and generates the result in the sum and the carry C2, i+1 . The carry-propagate subtractor 103 subtracts the sixth signal Zi of the i""th column and the input carry bits C3,i received from the previous bit generator (i.e., the carry-propagate subtractor (not shown) of an ixe2x88x921""th bit generator) from the sum outputted from the second carry-save adder 102.
The third carry-save adder 104 adds the sum outputted from the carry-propagate subtractor 103 and two input carries C1,i, C2,i received from the first and second carry-save adders (not shown) and generates the 1-bit sum and 1-bit output carry C4,i+1. Then, the carry-propagate adder 105 adds the sum outputted from the third carry-save adder 104 and the two input carries C4,i, C5,i respectively received from the third carry-save adder and the carry-propagate adder (not shown) of the ixe2x88x921""th bit generator, and generates the i""th bit ri and 1-bit output carry C5,i+1.
According to the above steps, the data is generated bit by bit from the respective bit generators (0-30) to determine the 31-bit random number r30:0. However, the related art random number generator applies the 30th output carry to the 0""th input carry so as to generate a 0""th bit, which is then propagated and used.
As described above, the related art random number generator has various disadvantages. The related art random number generator wraps around a carry bit to the 0""th bit generator so that its operating path becomes longer and increases a processing time for generating a random number.
The above references are incorporated by reference herein where appropriate for appropriate teachings of additional or alternative details, features and/or technical background.
An object of the present invention is to provide a random number generator that substantially overcomes one or more problems caused by disadvantages in the related art.
Another object of the present invention is to provide a high speed random number generator.
Another object of the present invention is to provide a random number generator having increased efficiency.
Another object of the present invention is to provide a random number generator that implements a Lehmer random number generator in a reduced calculation time.
Another object of the present invention is to provide a random number generator that generates a random number by adding a final output carry to a final sum generated from respective bit generators without applying an output carry of a more significant bit generator to a less significant bit generator.
Another object of the present invention is to provide a random number generator that generates a pseudo random number without wrap around calculations for the least significant bit.
To achieve the above-described objects in a whole or in parts, there is provided a random number generator according to the present invention that includes a bit generation section having a plurality of bit generators for generating a plurality of sum bits of a prescribed-bit number, a carry bit conversion section receiving a plurality of final output carries from a final bit generator of the plurality of bit generators and converting the received value to an output signal, and a random number generation section adding the output signal of the carry bit conversion section to the bits generated from the bit generation section to generate a random number.
To achieve the above-described objects in a whole or in parts, there is provided a random number generator according to the present invention that includes a bit generator circuit that receives an input value and respectively generates a first number and an output signal, a converter that receives the output signal and generates a second number and a random number generator that combines the first and second number to generate a random number.
To further achieve the above-described objects in a whole or in parts, there is provided a method of generating pseudo random numbers from an input value according to the present invention that includes receiving the input value, generating a plurality of least significant to most significant bits using a corresponding columns of a circulation convolution matrix and a plurality of bit generators, converting a first signal received from at least one bit generator of the plurality of bit generators to a second signal, combining the second signal and the plurality of bits to generate a random number, setting the input value to the random number and repeating the above steps.
Additional advantages, objects, and features of the invention will be set forth in part in the description which follows and in part will become apparent to those having ordinary skill in the art upon examination of the following or may be learned from practice of the invention. The objects and advantages of the invention may be realized and attained as particularly pointed out in the appended claims.